#include <iostream>
#include <type_traits>
#include <cassert>
#include <string>
#include <memory>
#include <string.h>

using std::cout;
using std::endl;
//using DataType = int;
template <class DataType>
class Queue {
    static constexpr size_t initCap_ {4};
    static constexpr size_t npos_ = -1;
public:
    using type = DataType;
    using pointer = DataType*;
    Queue(size_t cap)
        : data_(new DataType[(cap > initCap_ ? cap : initCap_)]), capacity_(cap)
    {
        static_assert(std::is_copy_assignable<DataType>::value,
            "DataType shall be trivially copy constructible");
        static_assert(std::is_move_assignable<DataType>::value,
            "DataType shall be trivially copy constructible");
        assert(capacity_ > 0);
    }

    ~Queue() = default;

    void pushData(const DataType& value) {
        if (++tailIdx_ == capacity_) {
            makeSpace();
        }
        data_[tailIdx_] = value;
    }

    void pushData(DataType&& value) {
        if (++tailIdx_ == capacity_) {
            makeSpace();
        }
        data_[tailIdx_] = std::move(value);
    }

    DataType* popData() {
        if (empty()) {
            return nullptr;
        }
        DataType* ret = &data_[headIdx_++];
        if (headIdx_ > tailIdx_) { // empty queue
            headIdx_ = 0;
            tailIdx_ = npos_;
        }
        return ret;
    }

    size_t capacity() const {
        return capacity_;
    }

    size_t size() const {
        return tailIdx_ == npos_ ? 0 : tailIdx_ - headIdx_ + 1;
    }

    bool empty() const {
        return tailIdx_ == npos_;
    }

private:
    void makeSpace() {
        if (size() < capacity_) {
            shiftData();
        } else {
            capacity_ *= 2;
            if (capacity_ >= initCap_) {
                expandSize();
            }
        }
    }

    void shiftData() {
        size_t elemNums = size();
        memmove(data_.get(), &data_[headIdx_], elemNums);
        headIdx_ = 0;
        tailIdx_ = elemNums - 1;
    }

    void expandSize() {
        std::unique_ptr<DataType[]> newData(new DataType[capacity_ * 2]);
        if (newData) {
            memcpy(newData.get(), data_.get(), initCap_);
            data_.swap(newData);
        } else {
            throw std::bad_alloc();
        }
    }
// protected so that Tester decorator can get access
protected:
    std::unique_ptr<DataType[]> data_; size_t headIdx_ {0};
    size_t tailIdx_ {npos_};
    size_t capacity_ {initCap_};
};

// Decorator CRTP for testing Queue
template <class Testee>
class Tester : public Testee {
public:
    using Testee::Testee;

    template <typename... Args>
    Tester(Args&&... args)
        : Testee(std::forward<Args>(args)...)
    {}

    typename Testee::type* popData() {
        typename Testee::type* ret = Testee::popData();
        cout << "---------POP---------\n";
        cout << "popped ";;
        if (ret == nullptr) {
            cout << "nullptr\n";
        } else {
            cout << *ret << endl;
        }
        cout << "cur head at " << Testee::headIdx_
             << " cur tail at " << Testee::tailIdx_ << endl;;
        return ret;
    }
    void pushData(typename Testee::type& val)
    {
        cout << "---------PUSH--------\n";
        cout << "pushing " << val
             << " original size = " << Testee::size() << endl;
        cout << "cur head at " << Testee::headIdx_
             << " cur tail at " << Testee::tailIdx_ << endl;;
        Testee::pushData(val);
        cout << "after push, cur size = " << Testee::size()
             << " capacity = " << Testee::capacity() << endl;
        cout << "cur head at " << Testee::headIdx_
             << " cur tail at " << Testee::tailIdx_ << endl;;
    }
};

int main(int argc, char** argv) {
    Tester<Queue<int>> q(2);
    int dummy = 666;
    for (int i = 0; i < 4; ++i) {
        q.pushData(i);
    }
    for (int i = 0; i < 5; ++i) {
        q.popData();
    }
    q.pushData(dummy);
    for (int i = 0; i < 4; ++i) {
        q.pushData(i);
    }
    for (int i = 0; i < 5; ++i) {
        q.popData();
    }
    for (int i = 0; i < 9; ++i) {
        q.pushData(i);
    }
    return 0;
}